package 动态规划;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 120. 三角形最小路径和
 *给定一个三角形 triangle ，找出自顶向下的最小路径和。

 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 * 思路： 这道题同样采用动态规划的思路
 *  问题核心：在三角形中找一条从顶部到底部的路径，使得路径上的数字之和最小。
 *  关键观察：每个位置的最小路径和 = 当前值 + 下一层相邻两个位置的最小路径和中的较小值。

    1：创建一个二维数组dp[][], dp[i][j]表示到达第i行第j列位置的最小路径和。
    2: 状态转移方程：
        对于每个元素triangle[i][j],其最小路径可以通过上一行的相邻元素的最小路径和加上当前元素的最小路径和计算。
        即状态转移方程为: dp[i][j] = triangle[i][j] + min(dp[i-1][j],dp[i-1][j-1])
    3:边界条件：
        第一行元素直接等于三角形的顶部元素，即dp[0][0] = triangle[0][0]
        每一行的第一个元素只能从上一行的第一个元素到达，即dp[i][0] = dp[i-1][0] + triangle[i][0]
        每一行的最后一个元素只能上一行的最后一个元素到达，即dp[i][i] = triangle[i][i] + dp[i-1][i-1]
    4：返回最后一行的最小值
 *
 */
public class L_120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // 定义二维数组
        int dp[][] = new int[n + 1][n + 1];
        dp[0][0] = triangle.get(0).get(0); // 初始化第一行
        for (int i = 1; i < n ; i++) {
            // 每一行的第一个元素
            dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
            // 每一行的最后一个元素
            dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
            // 中间段的元素,只能是从上一行相邻的两个元素中较小的一个
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + triangle.get(i).get(j);
            }
        }
        // 最后找出最后一行的最小值
        int min = dp[n-1][0];
        for (int i = 1; i < triangle.get(n-1).size(); i++) {
            min = Math.min(min,dp[n-1][i]);
        }
        return min;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入三角形的行数：");
        int n = scanner.nextInt();
        List<List<Integer>> triangle = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            System.out.println("请输入第" + (i + 1) + "行的元素个数：");
            int m = scanner.nextInt();
            List<Integer> row = new ArrayList<>(m);
            for (int j = 0; j < m; j++) {
                System.out.println("请输入第" + (i + 1) + "行的第" + (j + 1) + "个元素：");
                int element = scanner.nextInt();
                row.add(element);
            }
            triangle.add(row);
        }
        L_120 l120 = new L_120();
        int result = l120.minimumTotal(triangle);
        System.out.println("最小路径和为：" + result);
    }
}
